# Generate hir_type.inc.rs. To do this, we build up a DAG that
# represents a slice of the Ruby type hierarchy that we care about optimizing.
# This also includes cvalue values such as C booleans, int32, and so on.

require 'set'

# Type represents not just a Ruby class but a named union of other types.
class Type
  attr_accessor :name, :subtypes

  def initialize name, subtypes=nil
    @name = name
    @subtypes = subtypes || []
  end

  def all_subtypes
    subtypes.flat_map { |subtype| subtype.all_subtypes } + subtypes
  end

  def subtype name
    result = Type.new name
    @subtypes << result
    result
  end
end

# Helper to generate graphviz.
def to_graphviz_rec type, f
  type.subtypes.each {|subtype|
    f.puts type.name + "->" + subtype.name + ";"
  }
  type.subtypes.each {|subtype|
    to_graphviz_rec subtype, f
  }
end

# Generate graphviz.
def to_graphviz type, f
  f.puts "digraph G {"
  to_graphviz_rec type, f
  f.puts "}"
end

# ===== Start generating the type DAG =====

# Start at Any. All types are subtypes of Any.
any = Type.new "Any"
# Build the Ruby object universe.
value = any.subtype "RubyValue"
undef_ = value.subtype "Undef"
value.subtype "CallableMethodEntry"  # rb_callable_method_entry_t*
basic_object = value.subtype "BasicObject"
basic_object_exact = basic_object.subtype "BasicObjectExact"
basic_object_subclass = basic_object.subtype "BasicObjectSubclass"
$object = basic_object.subtype "Object"
object_exact = $object.subtype "ObjectExact"
object_subclass = $object.subtype "ObjectSubclass"
$subclass = [basic_object_subclass.name, object_subclass.name]
$builtin_exact = [basic_object_exact.name, object_exact.name]

$exact_c_names = {
  "ObjectExact" => "rb_cObject",
  "BasicObjectExact" => "rb_cBasicObject",
}

$inexact_c_names = {
  "Object" => "rb_cObject",
  "BasicObject" => "rb_cBasicObject",
}

# Define a new type that can be subclassed (most of them).
# If c_name is given, mark the rb_cXYZ object as equivalent to this exact type.
def base_type name, c_name: nil
  type = $object.subtype name
  exact = type.subtype(name+"Exact")
  subclass = type.subtype(name+"Subclass")
  if c_name
    $exact_c_names[exact.name] = c_name
    $inexact_c_names[subclass.name] = c_name
  end
  $builtin_exact << exact.name
  $subclass << subclass.name
  [type, exact]
end

# Define a new type that cannot be subclassed.
# If c_name is given, mark the rb_cXYZ object as equivalent to this type.
def final_type name, base: $object, c_name: nil
  if c_name
    $exact_c_names[name] = c_name
  end
  type = base.subtype name
  $builtin_exact << type.name
  type
end

base_type "String", c_name: "rb_cString"
base_type "Array", c_name: "rb_cArray"
base_type "Hash", c_name: "rb_cHash"
base_type "Range", c_name: "rb_cRange"
base_type "Set", c_name: "rb_cSet"
base_type "Regexp", c_name: "rb_cRegexp"
module_class, _ = base_type "Module", c_name: "rb_cModule"
class_ = final_type "Class", base: module_class, c_name: "rb_cClass"

numeric, _ = base_type "Numeric", c_name: "rb_cNumeric"

integer_exact = final_type "Integer", base: numeric, c_name: "rb_cInteger"
# CRuby partitions Integer into immediate and non-immediate variants.
fixnum = integer_exact.subtype "Fixnum"
integer_exact.subtype "Bignum"

float_exact = final_type "Float", base: numeric, c_name: "rb_cFloat"
# CRuby partitions Float into immediate and non-immediate variants.
flonum = float_exact.subtype "Flonum"
float_exact.subtype "HeapFloat"

symbol_exact = final_type "Symbol", c_name: "rb_cSymbol"
# CRuby partitions Symbol into immediate and non-immediate variants.
static_sym = symbol_exact.subtype "StaticSymbol"
symbol_exact.subtype "DynamicSymbol"

nil_exact = final_type "NilClass", c_name: "rb_cNilClass"
true_exact = final_type "TrueClass", c_name: "rb_cTrueClass"
false_exact = final_type "FalseClass", c_name: "rb_cFalseClass"

# Build the cvalue object universe. This is for C-level types that may be
# passed around when calling into the Ruby VM or after some strength reduction
# of HIR.
cvalue = any.subtype "CValue"
cvalue.subtype "CBool"
cvalue.subtype "CPtr"
cvalue.subtype "CDouble"
cvalue.subtype "CNull"
cvalue_int = cvalue.subtype "CInt"
signed = cvalue_int.subtype "CSigned"
unsigned = cvalue_int.subtype "CUnsigned"
[8, 16, 32, 64].each {|width|
  signed.subtype "CInt#{width}"
  unsigned.subtype "CUInt#{width}"
}

# Assign individual bits to type leaves and union bit patterns to nodes with subtypes
num_bits = 0
$bits = {"Empty" => ["0u64"]}
$numeric_bits = {"Empty" => 0}
Set[any, *any.all_subtypes].sort_by(&:name).each {|type|
  subtypes = type.subtypes
  if subtypes.empty?
    # Assign bits for leaves
    $bits[type.name] = ["1u64 << #{num_bits}"]
    $numeric_bits[type.name] = 1 << num_bits
    num_bits += 1
  else
    # Assign bits for unions
    $bits[type.name] = subtypes.map(&:name).sort
  end
}
[*any.all_subtypes, any].each {|type|
  subtypes = type.subtypes
  unless subtypes.empty?
    $numeric_bits[type.name] = subtypes.map {|ty| $numeric_bits[ty.name]}.reduce(&:|)
  end
}

# Unions are for names of groups of type bit patterns that don't fit neatly
# into the Ruby class hierarchy. For example, we might want to refer to a union
# of TrueClassExact|FalseClassExact by the name BoolExact even though a "bool"
# doesn't exist as a class in Ruby.
def add_union name, type_names
  type_names = type_names.sort
  $bits[name] = type_names
  $numeric_bits[name] = type_names.map {|type_name| $numeric_bits[type_name]}.reduce(&:|)
end

add_union "BuiltinExact", $builtin_exact
add_union "Subclass", $subclass
add_union "BoolExact", [true_exact.name, false_exact.name]
add_union "Immediate", [fixnum.name, flonum.name, static_sym.name, nil_exact.name, true_exact.name, false_exact.name, undef_.name]
$bits["HeapBasicObject"] = ["BasicObject & !Immediate"]
$numeric_bits["HeapBasicObject"] = $numeric_bits["BasicObject"] & ~$numeric_bits["Immediate"]
$bits["HeapObject"] = ["Object & !Immediate"]
$numeric_bits["HeapObject"] = $numeric_bits["Object"] & ~$numeric_bits["Immediate"]

# ===== Finished generating the DAG; write Rust code =====

puts "// This file is @generated by src/hir_type/gen_hir_type.rb."
puts "mod bits {"
$bits.keys.sort.map {|type_name|
  subtypes = $bits[type_name].join(" | ")
  puts "  pub const #{type_name}: u64 = #{subtypes};"
}
puts "  pub const AllBitPatterns: [(&str, u64); #{$bits.size}] = ["
# Sort the bit patterns by decreasing value so that we can print the densest
# possible to-string representation of a Type. For example, CSigned instead of
# CInt8|CInt16|...
$numeric_bits.sort_by {|key, val| -val}.each {|type_name, _|
  puts "    (\"#{type_name}\", #{type_name}),"
}
puts "  ];"
puts "  pub const NumTypeBits: u64 = #{num_bits};
}"

puts "pub mod types {
  use super::*;"
$bits.keys.sort.map {|type_name|
    puts "  pub const #{type_name}: Type = Type::from_bits(bits::#{type_name});"
}
puts "  pub const ExactBitsAndClass: [(u64, *const VALUE); #{$exact_c_names.size}] = ["
$exact_c_names.each {|type_name, c_name|
  puts "    (bits::#{type_name}, &raw const crate::cruby::#{c_name}),"
}
puts "  ];"
$inexact_c_names = $inexact_c_names.to_a.sort_by {|name, _| $bits[name]}.to_h
puts "  pub const InexactBitsAndClass: [(u64, *const VALUE); #{$inexact_c_names.size}] = ["
$inexact_c_names.each {|type_name, c_name|
  puts "    (bits::#{type_name}, &raw const crate::cruby::#{c_name}),"
}
puts "  ];"
puts "}"

File.open("zjit_types.dot", "w") do |f|
  to_graphviz(any, f)
end
